长序列求和 (longsum) 的题解

题目背景

AC_Automation 作为一个可爱的妹子，她喜欢求和与乘积，还特别喜欢长的东西。现在她给你一个很长的序列，想让你求一些东西。看在她那么可爱的份上，就帮帮她吧。

题目描述

她本来想给你一个很长的序列 $A$ ，但是为了让你解出题目，善良的她给了一个较短的序列 $B_n$ 来表示所有在序列 $A$ 的中的数。具体来讲，序列 $A$ 和序列 $B$ 之间的关系为：

A_{(i - 1) \times n^3 + (j - 1) \times n^2 + (k-1) \times n + l} = B_i \times B_j + B_k \times B_l

（其中 $1 \le i, j, k, l \le n$ ）

可以发现，序列 $A$ 的下标在 $1 \sim n^4$ 之间。她还定义了一个函数 $f(l, r)$ ，满足：

f(l, r) = \sum_{i = l}^{r}A_i = A_l + A_{l + 1} + \cdots + A_r

现在她给了你一个长度为 $n$ 的序列 $B_n$ ，以及 $T$ 个询问，对于第 $i$ 个询问 $l_i, r_i$ ，请你求出对应的 $f(l_i, r_i)$ 。因为她很讨厌高精度，为了满足她的要求，请你输出该值模上 $10^9 + 7$ 的值

由于她太菜了，看在她那么可爱的份上，就帮帮她吧。

输入格式

第一行两个整数 $n$ 和 $T$ ，分别表示序列长度和询问的个数

第二行 $n$ 个正整数 $B_i$ ，表示 AC_Automation 给你的一个序列。

接下来 $T$ 行，每行一个 $l_i$ 和 $r_i$ ，表示 $T$ 个询问。

输出格式

$T$ 行，表示每个 $l_i$ 和 $r_i$ 所对应的 $f(l_i, r_i)$ 模上 $10^9 + 7$ 的值

样例输入

样例输出

30
72
42

样例解释

A_{1} = 2, A_{2} = 3, A_{3} = 3, A_{4} = 5

A_{5} = 3, A_{6} = 4, A_{7} = 4, A_{8} = 6

A_{9} = 3, A_{10} = 4, A_{11} = 4, A_{12} = 6

A_{13} = 5, A_{14} = 6, A_{15} = 6, A_{16} = 8

f(1, 8) = A_{1} + A_{2} + A_{3} + A_{4} + A_{5} + A_{6} + A_{7} + A_{8} = 30

f(1, 16) = A_{1} + A_{2} + A_{3} + A_{4} + A_{5} + A_{6} + A_{7} + A_{8}\\ + A_{9} + A_{10} + A_{11} + A_{12} + A_{13} + A_{14} + A_{15} + A_{16} = 72

f(9, 16) = A_{9} + A_{10} + A_{11} + A_{12} + A_{13} + A_{14} + A_{15} + A_{16} = 42

数据范围与约定

测试点序号	$n\le$	$T\le$
$1 \sim 5$	$20$	$10^4$
$6 \sim 15$	$10^3$	$10^4$
$16 \sim 25$	$10^4$	$2 \times 10^5$

对于 $100\%$ 的数据， $1 \le n \le 10^4$ ， $1 \le l_i \le r_i \le n^4$ ， $1 \le T\le 2 \times 10^5$ ， $1 \le B_i \le 10^4$ 。

题解

没有前缀和的暴力，得 $4$ 分，有前缀和的暴力，得 $20$ 分。

我们来考虑如何得到这 $60$ 分。

可以发现，由于 $n^2 < 10^6$ ，所以我们可以写一个 $O(n^2 + T)$ 的算法。具体来讲，我们可以令一个二维数组 $C$ ，其中 $C_{i \cdot n + j} = B_i \cdot B_j$ 。那么 $B_i \cdot B_j + B_k \cdot B_l = C_{i \cdot n + j} + C_{k \cdot n + l}$

我们来看这个式子（其中假设 $B_i \cdot B_j = C_x$ ， $B_k \cdot B_l = C_y$ ，且 $A_p = B_i \cdot B_j + B_k \cdot B_l$ ）：

\sum_{p = l}^{r}A_p = C_x + C_y

具体来讲，每个 $A_p$ 所对应的 $C_x$ 和 $C_y$ 如下图：

假如 $n = 2, l = 2, r = 13$ ，我们就可以有这样的变换：

\sum_{p = 2}^{13} (C_x + C_y)

= (C_1 + C_3) + (C_1 + C_4) + (C_2 + C_1) + \cdots + (C_2 + C_4) + (C_3 + C_1) + \cdots + (C_3 + C_4) + (C_4+ C_1)

= 2 \cdot C_1 + (C_3 + C_4) + 4 \cdot (C_2 + C_3) + 2 \cdot (C_1 + C_2 + C_3 + C_4) + C_4 + C_1

我们令 $s_i = \sum^{i}_{p = 1} C_p, s_0 = 0$ （可以发现这是可以预处理的），那么

= 2 \cdot C_1 + (s_4 - s_2) + 4 \cdot (s_3 - s_1) + 2 \cdot s_4 + C_4 + (s_1 - s_0)

结构如下图：

同样，在 $n = 2, l = 7, r = 16$ 的时候，也有这样的变换：

\sum_{p = 2}^{13} C_x \cdot C_y = 1 \cdot C_2 + (s_4 - s_3) + 4 \cdot (s_4 - s_3) + 2 \cdot s_4